﻿using System.Text;

namespace Algorithm
{
    public class Program
    {

        public static void Main(string[] args)
        {
            #region Two Sum
            int[] intsForSum = { 15, 11, 7, 2 };
            int target = 9;
            var TwoSumResult = TwoSum(intsForSum, target);
            #endregion

            #region GroupAnagrams
            string[] strsForGroupAnagrams = { "eat", "tea", "tan", "ate", "nat", "bat" };
            var GruopAnagramsReuslt = GroupAnagrams(strsForGroupAnagrams);
            #endregion

            #region LongestConsecutive
            int[] intsForLongestConsecutive = { 100, 4, 200, 1, 3, 2 };
            var LongestConsecutiveResult = LongestConsecutive(intsForLongestConsecutive);
            #endregion

            #region MoveZeroes
            int[] intsForMoveZeroes = { 0, 1, 0, 3, 12 };
            MoveZeroes(intsForMoveZeroes);
            #endregion

            #region MaxArea
            int[] intsForMaxArea = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
            var MaxAreaResult = MaxArea(intsForMaxArea);
            #endregion

            #region ThreeSum
            int[] intForThreeSum = { -1, 0, 1, 2, -1, -4 };
            var ThreeSumResult = ThreeSum(intForThreeSum);
            #endregion

            #region Trap
            int[] intsForTrap = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
            var TrapResult = Trap(intsForTrap);
            #endregion

            #region LengthOfLongestSubstring
            string consiveString = "abcabcbb";
            var LengthOfLongestSubstringResult = LengthOfLongestSubstring(consiveString);
            #endregion

            #region FindAnagrams
            string originString = "cbaebabacd";
            string matchString = "abc";
            var FindAnagramsResult = FindAnagrams(originString, matchString);
            #endregion

            #region SubarraySum
            int[] intsForSubarraySum = { 1, 2, 3 };
            int targetForSubarray = 3;
            var SubarrayResult = SubarraySum(intsForSubarraySum, targetForSubarray);
            #endregion

            #region MaxSlidingWindow
            int[] intsForMaxSlid = { 1, 3, -1, -3, 5, 3, 6, 7 };
            int sizeForMaxSlid = 3;
            MaxSlidingWindow(intsForMaxSlid, sizeForMaxSlid);
            #endregion

            #region Merge
            int[][] intervals = new int[][] { new int[]{1, 4},
                                              new int[]{0, 2},
                                              new int[]{3, 5},};
            int[][] aintervals = new int[][] { new int[]{1, 4},
                                               new int[]{0, 0}
                                               };
            var MergeResult = Merge(intervals);
            #endregion

            #region Rotate
            var intsForRotate = new int[] { 1, 2, 3, 4, 5, 6, 7 };
            int kForRotate = 2;
            var resultForRotate = Rotate(intsForRotate, kForRotate);
            #endregion

            #region ProductExceptSelf
            var intsForProductExceptSelf = new int[] { 1, 2, 3, 4 };
            var resultForProductExceptSelf = ProductExceptSelf(intsForProductExceptSelf);
            #endregion

            #region FirstMissingPositive
            var intsForFirstMissing = new int[] { 1, 2, 0 };
            var resultForFirstMissing = FirstMissingPositive(intsForFirstMissing);
            #endregion

            #region SetZeroes
            var matrixForSetZeroes = new int[][] { new int[] {0,1,2,0 },
                                       new int[] {3,4,5,2 },
                                       new int[] {1,3,1,5 },};
            var matrixResult = SetZeroes(matrixForSetZeroes);
            #endregion

            #region SpiralOrder
            var matrixForSpiralOrder = new int[][] { new int[] { 1, 2, 3, 4},
                                                     new int[] { 5, 6, 7, 8 },
                                                     new int[] { 9, 10, 11, 12}};
            var spiralOrderResult = SpiralOrder(matrixForSpiralOrder);
            #endregion

            #region MaxProfit
            int[] intsForMaxProfit = new int[] { 7, 1, 5, 3, 6, 4 };
            var maxProfitResult = MaxProfit(intsForMaxProfit);
            #endregion

            #region NumIslands
            char[][] charForIsland = new char[][] {
                new char[] {'1','1','1','1','0'},
                new char[] {'1','1','0','1','0'},
                new char[] {'1','1','0','0','0'},
                new char[] {'0','0','0','0','0'},
            };
            var numsOfCharIslands = NumIslands(charForIsland);
            #endregion

            #region OrangesRotting
            var orangesGrid = new int[][] { new int[] {2,1,1 },
                                            new int[] {1,1,0 },
                                            new int[] {0,1,1 } };
            var orangeResult = OrangesRotting(orangesGrid);
            #endregion

            #region PivotIndex
            var pivotIndexNums = new int[] { 1, 7, 3, 6, 5, 6 };
            var pivotIndexResult = PivotIndex(pivotIndexNums);
            #endregion

            #region SearchInsert
            var searchInsertNums = new int[] { 1, 3, 5, 7 };
            var searchInsertTarget = 9;
            var searchInsertResult = SearchInsert(searchInsertNums, searchInsertTarget);
            #endregion

            #region MatrixRotate
            var matrixForRotate = new int[][]
            {
                new int[] {5, 1, 9, 11},
                new int[] {2, 4, 8, 10},
                new int[] {13, 3, 6, 7},
                new int[] {15, 14, 12, 16}};
            MatrixRotate(matrixForRotate);
            #endregion

            #region FindDiagonalOrder
            var matrixDiagonal = new int[][]
            {
                new int [] {1,2,3},
                new int [] {4,5,6},
                new int [] {7,8,9},
            };
            var findDiagonalorderResult = FindDiagonalOrder(matrixDiagonal);
            #endregion

            #region LongestCommonPrefix
            var strsForLongestCommonPrefix = new string[] { "flower", "flow", "flight" };
            var prefixResult = LongestCommonPrefix(strsForLongestCommonPrefix);
            #endregion

            #region ReverseWords
            string reverseString = "a good  example";
            var reverseResult = ReverseWords(reverseString);
            #endregion
        }


        /// <summary>
        /// Level: Easy
        /// 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        /// <exception cref="Exception"></exception>
        public static int[] TwoSum(int[] nums, int target)
        {
            Dictionary<int, int> map = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++)
            {
                //查找数字和的结果
                int complement = target - nums[i];

                if (map.ContainsKey(complement))
                {
                    //返回当前数字的下标，和与其和为target的数字的下标
                    return new int[] { map[complement], i };
                }

                if (!map.ContainsKey(nums[i]))
                {
                    //在Map中存储这个值和他的下标
                    map.Add(nums[i], i);
                }
            }
            throw new Exception("No two sum solution");
        }

        /// <summary>
        /// Level: Normal
        /// 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
        /// 例如:"eat" "ate" "tea" 这三个单词互为字母异位词。
        /// </summary>
        /// <param name="strs"></param>
        /// <returns></returns>
        public static IList<IList<string>> GroupAnagrams(string[] strs)
        {
            if (strs == null || strs.Length == 0) return new List<IList<string>>();
            Dictionary<string, List<string>> map = new Dictionary<string, List<string>>();
            foreach (string s in strs)
            {
                char[] ca = s.ToCharArray();
                //对字符串进行排序，例如'eat','ate','tea' 排序后都得到同一个序列: 'aet'.
                Array.Sort(ca);
                string keyStr = new string(ca);
                if (!map.ContainsKey(keyStr)) map.Add(keyStr, new List<string>());
                map[keyStr].Add(s);
            }
            return new List<IList<string>>(map.Values);
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int LongestConsecutive(int[] nums)
        {
            #region 个人方法 执行时间208ms 内存消耗67.5mb
            //var rnums = nums.Distinct();
            //var re = rnums.ToArray();
            //Array.Sort(re);
            //if (re == null || re.Length == 0) return 0;
            //if (re.Length == 1) return 1;
            //if (re.Length == 2)
            //{
            //    if (Math.Abs(re[0] - re[1]) == 1)
            //    {
            //        return 2;
            //    }
            //    else
            //    {
            //        return 1;
            //    }
            //}
            //int length = 1;
            //List<int> list = new List<int>();
            //for (int i = 0; i < re.Length - 1; i++)
            //{
            //    if (Math.Abs(re[i] - re[i + 1]) == 1)
            //    {
            //        length++;
            //    }
            //    else
            //    {
            //        list.Add(length);
            //        length = 1;
            //    }
            //    if (re.Length >= 3 && i == re.Length - 2)
            //    {
            //        list.Add(length);
            //    }
            //}
            //return list.Max();
            #endregion

            #region 好方法 执行时间173ms 内存消耗65.74mb
            var numSet = new HashSet<int>(nums);

            //使用List<int>会导致超时，性能远低于HashSet
            //List<int> numSet = new List<int>(nums);

            int longestStreak = 0;
            foreach (int num in numSet)
            {
                //先查找该数字的前一个数字是否是连续的
                if (!numSet.Contains(num - 1))
                {
                    int currentNum = num;
                    int currentStreak = 1;
                    //查找现在这个数字与后一个数字是否是连续的
                    while (numSet.Contains(currentNum + 1))
                    {
                        currentNum += 1;
                        currentStreak += 1;
                    }
                    //不断更新当前最长的连续长度
                    longestStreak = Math.Max(longestStreak, currentStreak);
                }
            }
            return longestStreak;
            #endregion
        }


        /// <summary>
        /// Level: Easy
        /// 给定一个数组nums,编写一个函数将所有的0移动到数组的末尾, 同时保证非零元素的相对顺序
        /// </summary>
        /// <param name="nums"></param>
        public static void MoveZeroes(int[] nums)
        {
            #region 个人方法，完全顺序 输入 {3,0,2,4,0,-1,9,12} 得到 {-1,2,3,4,9,12,0,0}
            //if (nums == null || nums.Length == 0) return;
            //int zeroCount = 0;
            //int firstIndex = -1;
            //foreach (int num in nums)
            //{
            //    if (num == 0)
            //    {
            //        zeroCount++;
            //    }
            //}
            //if (zeroCount == 0)
            //{
            //    return;
            //}
            //zeroCount = 0;

            //Array.Sort(nums);
            //foreach (var n in nums)
            //{
            //    if (n == 0)
            //    {
            //        if (firstIndex == -1)
            //        {
            //            firstIndex = n;
            //        }
            //        zeroCount++;
            //    }
            //}
            //if (zeroCount == 0)
            //{
            //    return;
            //}
            //for (int i = firstIndex; i < nums.Length - firstIndex - zeroCount; i++)
            //{
            //    nums[i] = nums[i + zeroCount];
            //}
            //for (int j = 0; j < zeroCount; j++)
            //{
            //    nums[nums.Length - 1 - j] = 0;
            //}
            #endregion

            #region 寻找到非0项便把后排数字向前移动 
            int lastNonZeroFoundAt = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != 0)
                {
                    //多琢磨这个坐标前移过程
                    nums[lastNonZeroFoundAt++] = nums[i];
                }
            }
            for (int i = lastNonZeroFoundAt; i < nums.Length; i++)
            {
                nums[i] = 0;
            }
            #endregion 
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。不可倾斜水杯。
        /// </summary>
        /// <param name="height"></param>
        /// <returns></returns>
        public static int MaxArea(int[] height)
        {
            #region 个人方法超时 尽量少使用多次循环嵌套
            //int max = 0;
            //for (int i = 0; i < height.Length; i++)
            //{
            //    for (int j = i + 1; j < height.Length; j++)
            //    {
            //        if (max < Math.Min(height[i], height[j]) * (j - i))
            //        {
            //            max = Math.Min(height[i], height[j]) * (j - i);
            //        }
            //    }
            //}
            //return max;
            #endregion

            #region 算左右长度方式检查宽度
            int maxArea = 0;
            int left = 0;
            int right = height.Length - 1;

            while (left < right)
            {
                int h = Math.Min(height[left], height[right]);
                int w = right - left;
                maxArea = Math.Max(maxArea, h * w);

                //始终以长边为基准
                if (height[left] < height[right])
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
            return maxArea;
            #endregion
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个数组nums,判断是否存在三元数组nums[i],nums[j],nums[k] 满足i != j, i != k, k != j, 同时满足nums[i]+nums[j]nums[k] == 0 
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static IList<IList<int>> ThreeSum(int[] nums)
        {
            Array.Sort(nums);
            IList<IList<int>> result = new List<IList<int>>();

            for (int i = 0; i < nums.Length - 2; i++)
            {
                if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip same results
                int j = i + 1, k = nums.Length - 1;
                while (j < k)
                {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == 0)
                    {
                        result.Add(new List<int> { nums[i], nums[j], nums[k] });
                        while (j < k && nums[j] == nums[j + 1]) j++; // Skip same results
                        while (j < k && nums[k] == nums[k - 1]) k--; // Skip same results
                        j++; k--;
                    }
                    else if (sum < 0)
                    {
                        j++;
                    }
                    else
                    {
                        k--;
                    }
                }
            }
            return result;
        }

        /// <summary>
        /// Level: Hard
        /// 给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少水
        /// </summary>
        /// <param name="height"></param>
        /// <returns></returns>
        public static int Trap(int[] height)
        {
            if (height == null || height.Length == 0) { return 0; }
            int left = 0; int right = height.Length - 1;
            int maxLeft = 0, maxRight = 0;
            int ans = 0;

            while (left < right)
            {
                if (height[left] < height[right])
                {
                    if (height[left] >= maxLeft)
                    {
                        maxLeft = height[left];
                    }
                    else
                    {
                        ans += maxLeft - height[left];
                    }
                    left++;
                }
                else
                {
                    if (height[right] >= maxRight)
                    {
                        maxRight = height[right];
                    }
                    else
                    {
                        ans += maxRight - height[right];
                    }
                    right--;
                }
            }
            return ans;
        }

        /// <summary>
        /// Level: Normal
        /// 给定字符串s，找出其中无重复字符的最长子串长度
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int LengthOfLongestSubstring(string s)
        {
            int n = s.Length;
            HashSet<char> set = new HashSet<char>();
            int ans = 0, i = 0, j = 0;
            while (i < n && j < n)
            {
                // 尝试扩展右边的窗口
                if (!set.Contains(s[j]))
                {
                    set.Add(s[j++]);
                    ans = Math.Max(ans, j - i);
                }
                else
                {
                    // 缩小左边的窗口
                    set.Remove(s[i++]);
                }
            }
            return ans;
        }

        /// <summary>
        /// Level: Normal
        /// 给定两个字符串s和p, 找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
        /// </summary>
        /// <param name="s"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        public static IList<int> FindAnagrams(string s, string p)
        {
            #region 个人方法，超时
            //IList<int> map = new List<int>();
            //char[] cp = p.ToCharArray();
            //Array.Sort(cp);
            //string cps = new string(cp);
            //string childCombo = string.Empty;
            //for (int i = 0; i < s.Length - p.Length + 1; i++)
            //{
            //    childCombo = s[i].ToString();
            //    for (int j = 1; j < p.Length; j++)
            //    {
            //        childCombo += s[i + j];
            //    }
            //    char[] cchildCombo = childCombo.ToCharArray();
            //    Array.Sort(cchildCombo);
            //    string cthreeCombos = new string(cchildCombo);
            //    if (cps == cthreeCombos)
            //    {
            //        map.Add(i);
            //    }
            //}
            //return map;
            #endregion

            #region 可用方法
            IList<int> result = new List<int>();
            if (s.Length < p.Length) return result;
            int[] pCount = new int[26];
            int[] sCount = new int[26];
            // 计算p中每个字符的数量
            for (int i = 0; i < p.Length; i++)
            {
                pCount[p[i] - 'a']++;
                sCount[s[i] - 'a']++;
            }
            if (IsMatch(pCount, sCount)) result.Add(0);
            for (int i = p.Length; i < s.Length; i++)
            {
                // 移动窗口
                sCount[s[i] - 'a']++;
                sCount[s[i - p.Length] - 'a']--;
                if (IsMatch(pCount, sCount)) result.Add(i - p.Length + 1);
            }

            return result;
        }

        public static bool IsMatch(int[] pCount, int[] sCount)
        {
            for (int i = 0; i < 26; i++)
            {
                if (pCount[i] != sCount[i]) return false;
            }
            return true;
            #endregion
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个整数数组nums和一个整数k, 返回该数组中和为k的子数组的个数
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int SubarraySum(int[] nums, int k)
        {
            int count = 0;
            int sum = 0;
            Dictionary<int, int> preSum = new Dictionary<int, int>();
            preSum[0] = 1;
            for (int i = 0; i < nums.Length; i++)
            {
                sum += nums[i];
                if (preSum.ContainsKey(sum - k))
                {
                    count += preSum[sum - k];
                }
                if (!preSum.ContainsKey(sum))
                {
                    preSum[sum] = 0;
                }
                preSum[sum]++;
            }
            return count;
        }

        /// <summary>
        /// Level: Hard
        /// 给定一个整数数组nums，有一个大小为k的滑动窗口从数组的最左边移动到数组的最右边，视野范围限定在滑动窗口内的k个数字，滑动窗口每次只向右边移动一位,返回窗口中的最大值
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int[] MaxSlidingWindow(int[] nums, int k)
        {
            #region 双循环队列线性扫描 (会超时) 复杂度O(kn)
            List<int> ints = new List<int>();
            int max = 0;
            if (nums.Length == 1)
            {
                ints.Add(nums[0]);
                return ints.ToArray();
            }
            if (k == 1)
            {
                return nums;
            }
            for (int i = 0; i < nums.Length - k + 1; i++)
            {
                int right = i + k - 1;
                int left = i;
                while (left != right)
                {
                    if (nums[left] < nums[right])
                    {
                        max = nums[right];
                        left++;
                    }
                    else
                    {
                        max = nums[left];
                        right--;
                    }
                }
                ints.Add(max);
            }
            return ints.ToArray();
            #endregion

            #region 用双端队列方式，不会超时，时间复杂度为O(k)
            if (nums == null || nums.Length == 0) return new int[0];
            LinkedList<int> deque = new LinkedList<int>();
            int[] result = new int[nums.Length - k + 1];
            for (int i = 0; i < nums.Length; i++)
            {
                if (deque.Count > 0 && deque.First.Value < i - k + 1)
                {
                    deque.RemoveFirst();
                }
                while (deque.Count > 0 && nums[deque.Last.Value] < nums[i])
                {
                    deque.RemoveLast();
                }
                deque.AddLast(i);
                if (i - k + 1 >= 0)
                {
                    result[i - k + 1] = nums[deque.First.Value];
                }
            }
            return result;
            #endregion
        }

        /// <summary>
        /// Level: Normal
        /// 给定整数数组nums，找出一个具有最大和的连续子数组（最少包含一个元素），返回其最大和
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MaxSubArray(int[] nums)
        {
            #region 方法1
            if (nums == null || nums.Length == 0) return 0;
            int maxSum = nums[0]; // 初始化最大和为数组的第一个元素
            int currentSum = nums[0]; // 初始化当前和为数组的第一个元素
            for (int i = 1; i < nums.Length; i++)
            {
                // 如果当前和小于0，那么对于求和来说没有贡献，所以将当前和更新为当前元素
                if (currentSum < 0)
                {
                    currentSum = nums[i];
                }
                else
                {
                    // 如果当前和大于等于0，那么对于求和来说有贡献，所以将当前元素加到当前和上
                    currentSum += nums[i];
                }
                // 更新最大和
                if (currentSum > maxSum)
                {
                    maxSum = currentSum;
                }
            }
            return maxSum;
            #endregion

            #region 方法2
            int res = nums[0];
            int sum = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                sum = Math.Max(nums[i], nums[i] + sum);
                res = Math.Max(sum, res);
            }
            #endregion
        }

        /// <summary>
        /// Level: Normal
        /// 以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [Start(i), end(1i)]，请合并所有重叠的区间，返回一个不重叠的区间数组，改数组需要恰好覆盖输入中的所有区间
        /// </summary>
        /// <param name="intervals"></param>
        /// <returns></returns>
        public static int[][] Merge(int[][] intervals)
        {
            #region  个人方法1
            //List<int[]> result = new List<int[]>();
            //int start = 0;
            //int end = 0;
            //bool maxLimit = false;
            //bool minLimit = false;
            //int[] newints = new int[2];
            //bool hasMerge = false;
            //bool first = true;
            //if (intervals == null || intervals.Length == 0)
            //{
            //    return null;
            //}
            //if (intervals.Length == 1)
            //{
            //    return intervals;
            //}
            //for (int i = 0; i < intervals.Length - 1; i++)
            //{
            //    if (hasMerge == false)
            //    {
            //        start = intervals[i][1];
            //        end = intervals[i + 1][0];
            //    }
            //    else
            //    {
            //        start = newints[1];
            //        end = intervals[i + 1][0];
            //    }
            //    //if (start < end)
            //    if (Math.Max(intervals[i][0], intervals[i][1]) < Math.Min(intervals[i + 1][0], intervals[i + 1][1])
            //        || Math.Max(intervals[i + 1][0], intervals[i + 1][1]) < Math.Min(intervals[i][0], intervals[i][1]))
            //    {
            //        if (!result.Contains(newints) && hasMerge == true)
            //        {
            //            result.Add(newints);
            //        }
            //        if (hasMerge == false)
            //        {
            //            result.Add(intervals[i]);
            //        }
            //        if (i == intervals.Length - 2 && (Math.Max(intervals[i][0], intervals[i][1]) < Math.Min(intervals[i + 1][0], intervals[i + 1][1])
            //        || Math.Max(intervals[i + 1][0], intervals[i + 1][1]) < Math.Min(intervals[i][0], intervals[i][1])))
            //        {
            //            result.Add(intervals[i + 1]);
            //        }
            //        hasMerge = false;
            //    }
            //    else
            //    {
            //        if (first)
            //        {
            //            newints = new int[] {Math.Min(Math.Min(Math.Min(intervals[i][0], intervals[i][1]), intervals[i+1][0]),intervals[i+1][1]),
            //                                 Math.Max(Math.Max(Math.Max(intervals[i][0], intervals[i][1]), intervals[i+1][0]),intervals[i+1][1])};
            //            first = false;
            //        }
            //        else
            //        {
            //            newints = new[] { Math.Min(Math.Min(Math.Min(newints[0], newints[1]), intervals[i + 1][0]), intervals[i + 1][1]),
            //                              Math.Max(Math.Max(Math.Max(newints[0], newints[1]), intervals[i + 1][0]), intervals[i + 1][1]) };
            //        }
            //        result.Add(newints);
            //        hasMerge = true;
            //    }
            //}
            //return result.ToArray();
            #endregion

            #region 可用方法
            if (intervals.Length <= 1)
                return intervals;
            List<int[]> result = new List<int[]>();
            Array.Sort(intervals, (a, b) => a[0] - b[0]);
            int[] currentInterval = intervals[0];
            result.Add(currentInterval);
            foreach (var interval in intervals)
            {
                int currentEnd = currentInterval[1];
                int nextBegin = interval[0];
                int nextEnd = interval[1];
                if (currentEnd >= nextBegin)
                {
                    currentInterval[1] = Math.Max(currentEnd, nextEnd);
                }
                else
                {
                    currentInterval = interval;
                    result.Add(currentInterval);
                }
            }
            return result.ToArray();
            #endregion
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int[] Rotate(int[] nums, int k)
        {
            //取余法
            int[] newNums = new int[nums.Length];
            for (int i = 0; i < nums.Length; i++)
            {
                newNums[(i + k) % nums.Length] = nums[i];
            }
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = newNums[i];
            }
            return nums;
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个整数数组nums,返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int[] ProductExceptSelf(int[] nums)
        {
            int[] answer = new int[nums.Length];
            answer[0] = 1;
            for (int i = 1; i < nums.Length; i++)
            {
                //answer[i]表示nums[i]左侧所有元素的乘积
                //因为nums[0]的左侧没有元素，所以answer[0] = 1
                answer[i] = nums[i - 1] * answer[i - 1];
            }
            //R为右侧所有元素的乘积
            //右边无元素，所以R初始为1
            int r = 1;
            for (int i = nums.Length - 1; i >= 0; i--)
            {
                answer[i] = answer[i] * r;
                r *= nums[i];
            }
            return answer;
        }

        /// <summary>
        /// Level: Hard
        /// 给定一个未排序的整数数组nums,找出其中没有出现的最小正整数
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int FirstMissingPositive(int[] nums)
        {
            #region 个人方法1，耗时197ms,内存62mb
            //Array.Sort(nums);
            //int count = 0;
            //if (!nums.Contains(1))
            //{
            //    return 1;
            //}
            //if (nums.Length == 1 && nums.Contains(1))
            //{
            //    return 2;
            //}
            //if (nums[nums.Length - 1] == 1)
            //{
            //    return 2;
            //}
            //for (int i = 0; i < nums.Length - 1; i++)
            //{
            //    if (nums[i + 1] - nums[i] != 1 && nums[i + 1] != 1 && nums[i + 1] > 0 && nums[i] > 0 && nums[i + 1] != nums[i])
            //    {
            //        return nums[i] + 1;
            //    }
            //    else
            //    {
            //        count++;
            //    }
            //}
            //if (count == nums.Length - 1)
            //{
            //    return nums[nums.Length - 1] + 1;
            //}
            //else
            //{
            //    return 0;
            //}
            #endregion

            #region 个人方法2，耗时2000ms,内存67mb
            Array.Sort(nums);
            List<int> minList = new List<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] <= 0)
                {
                    continue;
                }
                minList.Add(nums[i]);
            }
            if (!minList.Contains(1))
            {
                return 1;
            }
            minList.Distinct();
            var min = minList.Min();
            while (minList.Contains(min))
            {
                min++;
            }
            return min;
            #endregion
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个m x n 的矩阵，如果一个元素为0，则将其所在的行和列设置为0，使用原地算法
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public static int[][] SetZeroes(int[][] matrix)
        {
            #region 个人方法
            //List<int> positionX = new List<int>();
            //List<int> positionY = new List<int>();
            //for (int i = 0; i < matrixForSetZeroes.Length; i++)
            //{
            //    for (int j = 0; j < matrixForSetZeroes.Length; j++)
            //    {
            //        if (matrixForSetZeroes[i][j] == 0)
            //        {
            //            positionX.Add(i);
            //            positionY.Add(j);
            //        }
            //    }
            //}
            //for (int x = 0; x < positionX.Count; x++)
            //{
            //    for (int y = 0; y < positionY.Count; y++)
            //    {
            //        if (x - 1 >= 0 && y - 1 >= 0)
            //        {
            //            matrixForSetZeroes[x - 1][y - 1] = 0;
            //        }
            //        if (x - 1 >= 0 && y - 1 < 0)
            //        {
            //            matrixForSetZeroes[x - 1][y] = 0;
            //        }
            //        if (x - 1 < 0 && y - 1 >= 0)
            //        {
            //            matrixForSetZeroes[x][y - 1] = 0;
            //        }
            //        if (x + 1 < matrixForSetZeroes.Length && y + 1 <= matrixForSetZeroes.Length)
            //        {
            //            matrixForSetZeroes[x + 1][y + 1] = 0;
            //        }
            //        if (x + 1 < matrixForSetZeroes.Length && y + 1 >= matrixForSetZeroes.Length)
            //        {
            //            matrixForSetZeroes[x + 1][y] = 0;
            //        }
            //        if (x + 1 >= matrixForSetZeroes.Length && y + 1 < matrixForSetZeroes.Length)
            //        {
            //            matrixForSetZeroes[x][y + 1] = 0;
            //        }
            //    }
            //}
            //return matrixForSetZeroes;
            #endregion

            #region 可用方法二
            bool isCol = false;
            int R = matrix.Length;
            int C = matrix[0].Length;

            for (int i = 0; i < R; i++)
            {
                if (matrix[i][0] == 0)
                {
                    isCol = true;
                }

                for (int j = 1; j < C; j++)
                {
                    if (matrix[i][j] == 0)
                    {
                        matrix[0][j] = 0;
                        matrix[i][0] = 0;
                    }
                }
            }

            for (int i = 1; i < R; i++)
            {
                for (int j = 1; j < C; j++)
                {
                    if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    {
                        matrix[i][j] = 0;
                    }
                }
            }

            if (matrix[0][0] == 0)
            {
                for (int j = 0; j < C; j++)
                {
                    matrix[0][j] = 0;
                }
            }

            if (isCol)
            {
                for (int i = 0; i < R; i++)
                {
                    matrix[i][0] = 0;
                }
            }
            return matrix;
            #endregion
        }

        /// <summary>
        /// Level: Normal
        /// 给定一个m x n 的矩阵，请按照顺时针螺旋顺序，返回矩阵中所有的元素
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public static IList<int> SpiralOrder(int[][] matrix)
        {
            List<int> res = new List<int>();
            if (matrix.Length == 0) return res;
            int rowBegin = 0;
            int rowEnd = matrix.Length - 1;
            int colBegin = 0;
            int colEnd = matrix[0].Length - 1;

            while (rowBegin <= rowEnd && colBegin <= colEnd)
            {
                // Traverse Right
                for (int j = colBegin; j <= colEnd; j++)
                {
                    res.Add(matrix[rowBegin][j]);
                }
                rowBegin++;

                // Traverse Down
                for (int j = rowBegin; j <= rowEnd; j++)
                {
                    res.Add(matrix[j][colEnd]);
                }
                colEnd--;

                if (rowBegin <= rowEnd)
                {
                    // Traverse Left
                    for (int j = colEnd; j >= colBegin; j--)
                    {
                        res.Add(matrix[rowEnd][j]);
                    }
                }
                rowEnd--;

                if (colBegin <= colEnd)
                {
                    // Traver Up
                    for (int j = rowEnd; j >= rowBegin; j--)
                    {
                        res.Add(matrix[j][colBegin]);
                    }
                }
                colBegin++;
            }
            return res;
        }

        /// <summary>
        /// Level: Easy
        /// 给定数组price，他的第i个元素指第i天的股票价格，请计算最大利润。
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public static int MaxProfit(int[] prices)
        {
            int minPrice = int.MaxValue;
            int maxProfit = 0;
            for (int i = 0; i < prices.Length; i++)
            {
                if (prices[i] < minPrice)
                    minPrice = prices[i];
                else if (prices[i] - minPrice > maxProfit)
                    maxProfit = prices[i] - minPrice;
            }
            return maxProfit;
        }

        /// <summary>
        /// Level: Normal Type: DFS 深度优先搜索
        /// 给定由1(陆地)和0(海水)组成的二维网络，计算平面中的岛屿数量，岛屿总是被水包围，每座岛屿只会被水平和竖直方向的相邻的陆地连接形成，此外，网格四边均为海水
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public static int NumIslands(char[][] grid)
        {
            DeepSearchWay dsw = new DeepSearchWay();
            return dsw.NumIslands(grid);
        }

        /// <summary>
        /// Level: Normal Type: BFS 广度优先搜索
        /// 在给定的 M x N 网格中，方格内的腐烂橘子每分钟都会腐化相邻的新鲜橘子，返回网格内没有新鲜橘子为止所需要经过的最短时间，如果无法达成，则返回-1.
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public static int OrangesRotting(int[][] grid)
        {
            int[] dr = new int[] { -1, 0, 1, 0 };
            int[] dc = new int[] { 0, -1, 0, 1 };
            int m = grid.Length;
            int n = grid[0].Length;
            Queue<int> queue = new Queue<int>();

            IDictionary<int, int> depth = new Dictionary<int, int>();
            for (int r = 0; r < m; ++r)
            {
                for (int c = 0; c < n; ++c)
                {
                    if (grid[r][c] == 2)
                    {
                        int code = r * n + c;
                        queue.Enqueue(code);
                        depth.Add(code, 0);
                    }
                }
            }
            int ans = 0;
            while (queue.Count > 0)
            {
                int code = queue.Dequeue();
                int r = code / n;
                int c = code % n;
                for (int k = 0; k < 4; ++k)
                {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (0 <= nr && nr < m && 0 <= nc && nc < n && grid[nr][nc] == 1)
                    {
                        grid[nr][nc] = 2;
                        int ncode = nr * n + nc;
                        queue.Enqueue(ncode);
                    }
                }
            }
            foreach (int[] row in grid)
            {
                foreach (int v in row)
                {
                    if (v == 1)
                    {
                        return -1;
                    }
                }
            }
            return ans;
        }

        /// <summary>
        /// ExtraQuestion|前缀和
        /// 找出中心索引，中心索引代指，下标为中心索引时，中心索引左边的和等于中心索引右边的和
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int PivotIndex(int[] nums)
        {
            int total = 0;
            foreach (int num in nums)
            {
                total += num;
            }
            int sum = 0;
            for (int i = 0; i < nums.Length; ++i)
            {
                if (sum * 2 + nums[i] == total)
                {
                    return i;
                }
                sum += nums[i];
            }
            return -1;
        }

        /// <summary>
        /// 给定一个排序数组和目标值，在数组找到目标值，并返回索引，若目标值不存在数组中，返回他将按顺序插入的位置。时间复杂度O(log n)
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static int SearchInsert(int[] nums, int target)
        {
            #region 方法一
            //if (nums.Contains(target))
            //{
            //    for (int i = 0; i < nums.Length; i++)
            //    {
            //        if (nums[i] == target)
            //        {
            //            return i;
            //        }
            //    }
            //}
            //else
            //{
            //    if (target < nums[0])
            //    {
            //        return 0;
            //    }
            //    if (target > nums[nums.Length - 1])
            //    {
            //        return nums.Length;
            //    }
            //    for (int i = 0; i < nums.Length - 1; i++)
            //    {
            //        if (nums[i] < target && target < nums[i + 1])
            //        {
            //            return i + 1;
            //        }
            //    }
            //}
            //return nums.Length;
            #endregion

            #region 方法二
            int left = 0;
            int right = nums.Length - 1;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target)
                {
                    return mid;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            return left;
            #endregion
        }

        /// <summary>
        /// 给定一个 N x N 的二维矩阵matrix表示一个图像。将其旋转90°
        /// </summary>
        /// <param name="matrix"></param>
        public static void MatrixRotate(int[][] matrix)
        {
            //从外圈依次到中心处理，每次只需要处理每行的[i, len - i - 1]范围内的元素，让他们和对应的元素们交换
            if (matrix[0].Length == 1) return;
            int r = 0, c = matrix.Length - 1;
            for (int i = 0; i < matrix.Length / 2; i++)
            {
                for (int j = 0; j < (c - r); j++)
                {
                    int temp = matrix[r][r + j];
                    matrix[c - j][r] = matrix[c][c - j];
                    matrix[c][c - j] = matrix[r + j][c];
                    matrix[r + j][c] = temp;
                }
                r++;
                c--;
            }
        }

        /// <summary>
        /// 对一个矩阵进行对角线遍历
        /// </summary>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public static int[] FindDiagonalOrder(int[][] matrix)
        {
            if (matrix == null || matrix.Length == 0) return new int[0];
            int m = matrix.Length, n = matrix[0].Length;
            int row = 0, col = 0;
            int direction = 1;
            int[] result = new int[m * n];
            for (int i = 0; i < m * n; i++)
            {
                result[i] = matrix[row][col];
                row -= direction;
                col += direction;
                if (row >= m) { row = m - 1; col += 2; direction = -direction; }
                if (col >= n) { col = n - 1; row += 2; direction = -direction; }
                if (row < 0) { row = 0; direction = -direction; }
                if (col < 0) { col = 0; direction = -direction; }
            }
            return result;
        }

        /// <summary>
        /// 查找公共前缀，若不存在则返回空字符串""
        /// </summary>
        /// <param name="strs"></param>
        /// <returns></returns>
        public static string LongestCommonPrefix(string[] strs)
        {
            for (int i = 0; i < strs[0].Length; i++)
            {
                char c = strs[0][i];
                for (int j = 1; j < strs.Length; j++)
                {
                    if (i == strs[j].Length || strs[j][i] != c)
                    {
                        return strs[0].Substring(0, i);
                    }
                }
            }
            return strs[0];
        }

        /// <summary>
        /// 给定一个字符串s，找到其中最长的回文。
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string LongestPalindrome(string s)
        {
            Palindrome palindrome = new Palindrome();
            return palindrome.LongestPalindrome(s);
        }

        /// <summary>
        /// 翻转整个字符串，以空格为间隔，多个空格连结要统合为一个空格
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string ReverseWords(string s)
        {
            s = s.Trim();
            StringBuilder sb = new StringBuilder();
            List<string> words = new List<string>();
            string result = string.Empty;
            for (int i = 0; i < s.Length; i++)
            {
                char c = s[i];
                
                if (c != ' ')
                {
                    sb.Append(c);
                }
                if ((c == ' ' || i == s.Length - 1 ) && sb.ToString() != "")
                {

                    words.Add(sb.ToString());
                    sb = new StringBuilder();
                }
            }
            for (int i = words.Count() - 1; i >= 0; i--)
            {
                if (i != 0)
                {
                    result += words[i] + " ";
                }
                else
                {
                    result += words[i];
                }
            }
            return result;
        }

        /// <summary>
        /// 给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从0开始）。如果needle不是haystack的一部分，则返回-1。
        /// </summary>
        /// <param name="haystack"></param>
        /// <param name="needle"></param>
        /// <returns></returns>
        public int StrStr(string haystack, string needle)
        {
            for(int i = 0; i <= haystack.Length - needle.Length; i++)
            {
                int j;
                for (j = 0; j < needle.Length; j++)
                {
                    if (haystack[i + j] != needle[j]) break;
                }
                if(j == needle.Length)
                {
                    return i;
                }
            }
            return -1;
        }


        //注释测试
        public static void MethodOut()
        {
            int x = 0;
            void MethodInner()
            {
                Console.WriteLine("Inner Method");
            }
        }
    }
}